• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Techniques for improving the copy-to-write functionality in an SSD are described. In some embodiments, these techniques may be implemented as a method for providing enhanced SSD write copy functionality of providing, in the memory of a device, a structure for indirection data. The data structure may include a master entry for cloned data, the master entry having a reference to one or more indexes and a clone entry for the cloned data, the cloned entry including at least one of the following: a reference to a master index, a reference to a next index, and a value indicating an end of a data structure. These techniques may include browsing, using a computer processor, one or more copies of the cloned data using one or more of the references.
    公开号:FR3033061A1
    申请号:FR1651107
    申请日:2016-02-11
    公开日:2016-08-26
    发明作者:Dylan Mark Dewitt；Adam Michael Espeseth；Colin Christopher Mccambridge；David George Dreyer
    申请人:HGST Netherlands BV；
    IPC主号:
    专利说明:

    [0001] BACKGROUND OF THE INVENTION [0001] The Express Non-Volatile Memory (NVMe) Specification is a specification for access to semiconductor devices (SSDs, Solid-State Devices, State Devices) and other target devices connected through an Express Peripheral Component Interconnect Express (PCIe) bus. The PCIe Host Interface for SSD NVMe defines a Namespaces concept, which is analogous to logical volumes supported by SAS Redundant Array of Independent Disks (SAS) adapters. The copy-to-write functionality in an SSD can be implemented using namespaces. Namespaces are typically implemented as abstraction over the global logical block address (LBA) space pursued in the indirection system of an SSD. [0002] LBA metadata indicate only one host LBA and they do not include a reference account. Including or adding a reference account in the metadata would lead to additional writes to overwrite the data with new metadata, this being a bad solution. Without such reference counts in the LBA metadata, there is no mechanism to determine whether there are additional cloned copies (for example, the fact that additional LBAs are pointing to the same data). The management of multiple copies of data cloned on an SSD therefore faces particular difficulties with regard to the recovery of memory space. For example, when a host modifies the "source" LBA after a copy operation, it may lead to difficulties in recovering memory space. The source copy may actually be the "master" copy that was written before the copy operation was performed to duplicate the data on an additional host LBA or more. When this master LBA is changed, a non-copy-sensitive memory space recovery algorithm can release the physical data at the next opportunity, since there is no method for effectively changing the metadata of this data to indicate that more host LBAs are pointing to this data.
    [0002] SUMMARY OF THE INVENTION [0003] Techniques for improving the write copy functionality in an SSD are described. In some embodiments, the techniques may be embodied as a method for providing enhanced SSD write copy functionality of providing, in the memory of a PCIe device, an indirection data structure. The data structure may include a master entry for an original or source copy of the cloned data, the master entry having a reference to a master index and a reference to a next index, a clone entry for the cloned data, the entry cloned with a reference to the master index and a reference to a next index.
    [0003] Such techniques may include browsing, by means of a computer processor, one or more copies of the cloned data using one or more of the references. [0004] In accordance with further aspects of this exemplary embodiment, the host device may include at least one of: an enterprise server, a database server, a workstation, and a computer. [0005] According to further aspects of this exemplary embodiment, the indirection data structure may include a plurality of physical addresses. [0006] In accordance with other aspects of this exemplary embodiment, the indirection data structure may be part of a circular linked list, the master entry for cloned data including a reference to a master index and a reference to a next index 20. [0007] In accordance with other aspects of this exemplary embodiment, the indirection data structure may be part of a circular linked list, the clone input for the cloned data including a reference to the index master and a reference to a next index. [0008] In accordance with further aspects of this exemplary embodiment, the indirection data structure may be part of a single-end linked list, an entry contained in an index providing an indication that the 'index is a master index. According to other aspects of this exemplary embodiment, the references may consist of entries in an absolute indirection table for the addressing of logical blocks. [0010] In accordance with other aspects of this exemplary embodiment, the references may include entries in a tree data structure for logical block addressing. In accordance with further aspects of this exemplary embodiment, the enhanced copy-to-write functionality may include enhanced namespace copy functionality. In accordance with other aspects of this exemplary embodiment, the techniques may include positioning an indicator for one or more condensed logic blocks to indicate that said one or more condensed logic blocks are cloned. [0013] In accordance with other aspects of this exemplary embodiment, a master index of the master entry may point to the master entry. In accordance with further aspects of this exemplary embodiment, the master index of the cloned input may point to the master input. According to other aspects of this exemplary embodiment, the next index of a last cloned input in a data structure may point to the master entry. [0016] In accordance with other aspects of this exemplary embodiment, the techniques may include determining that the clone input for the cloned data is a single clone input, the determination being that the index following the cloned input matches the master index of the cloned input, determine that the next index of the master input points to the clone input, unblock the clone input of the cloned data by setting 25 l next index of the clone entry to an indirection input indicating a condensed logic block and setting the master index entry to an indirection input indicating a condensed logic block, and disabling the master entry of the cloned data by setting the next index of the master input to a first indirection input indicating a first condensed logic block of an original master input and setting the master index of the master input to a second indirection input indicating a second condensed logic block of the original master input. According to additional aspects of this exemplary embodiment, the techniques may include determining that the clone input for the cloned data is one of a plurality of clone inputs, the determination being determining at least one of the following: that the next index of the cloned entry does not match the master index of the cloned entry, and that the next index of the master entry does not point to clone entry, and unclone the clone entry of the cloned data by setting the next index of a previous entry so that it points to an entry indicated by the next index of the clone entry. According to other aspects of this exemplary embodiment, the techniques may include examining an input during a memory space recovery process, determining that the input contains a cloned indicator, and determining that the The input involved in the memory space recovery process is a valid entry that should not be deleted based on the determination that the entry contains the cloned flag. In other embodiments, the techniques may be implemented in the form of a computer program product consisting of a series of executable instructions on a computer. The computer program product may implement a process for providing enhanced copy-to-write functionality in an SSD. The computer program may implement the steps of providing, in the memory of a device, an indirection data structure comprising a master entry for cloned data, the master entry having a reference to one or more indexes , a clone entry for the cloned data, the cloned entry having at least one of: a reference to a master index, a reference to a next index, and a value indicating an end of a clone structure. data, and browse, by means of a computer processor, one or more copies of the cloned data using one or more of the references. In still other embodiments, the techniques may be implemented in the form of a system for providing enhanced copy functionality for writing to an SSD. The system may include a first device, wherein the first device includes stored instructions, which are stored in memory. The instructions may include an instruction to provide, in the memory of the first device, an indirection data structure comprising a master entry for cloned data, the master entry including a reference to one or more indexes, an entry clone for cloned data, the cloned entry having at least one of: a reference to a master index, a reference to a next index, and a value indicating an end of a data structure, and browse, by means of a computer processor, one or more copies of the cloned data using one or more of the references. [0021] In accordance with further aspects of this exemplary embodiment, the indirection data structure may comprise a plurality of physical addresses. According to other aspects of this exemplary embodiment, the indirection data structure may be part of a circular linked list, the master entry for cloned data including a reference to a master index and a reference to a next index. According to other aspects of this exemplary embodiment, the indirection data structure may be part of a circular linked list, the clone input for the cloned data including a reference to the master index and a reference to a next index. [0024] In accordance with further aspects of this exemplary embodiment, the indirection data structure may be part of a single-end linked list, an entry contained in an index providing an indication that the 'index is a master index. In accordance with other aspects of this exemplary embodiment, the references may include entries in an absolute indirection table for addressing logical blocks. In accordance with other aspects of this exemplary embodiment, the first device may include an Express Peripheral Component Interconnection (PCIe) device. In accordance with further aspects of this exemplary embodiment, the techniques may further comprise an instruction for positioning an indicator 3033061 for one or more condensed logic blocks to indicate that said one or more condensed logic blocks are cloned. . According to other aspects of this exemplary embodiment, the master index of the master input and the master index of the cloned input may point to the master input and the next index of the master input and the master index of the cloned input. a last entry cloned into a data structure that points to the master entry. According to additional aspects of this exemplary embodiment, the target device (e.g., a PCIe device) may include at least one of the following: a graphics processing unit, an audio acquisition card / video, a hard disk, a host bus adapter, and an Express Non-Volatile Memory (NVMe) controller. According to some embodiments, the target device may be a device that complies with the NVMe standard. The present invention will now be described in more detail with reference to exemplary embodiments thereof, as illustrated in the accompanying drawings.
    [0004] Although the present invention will be described hereinafter with reference to exemplary embodiments, it is to be understood that the present invention is not limited thereto. Those of ordinary skill in the art having access to the guidelines presented herein will be able to consider other embodiments, variations, and embodiments, as well as other fields of use, which fall within the scope of the present invention as described in US Pat. it is described herein, and to which the present invention may be of great utility. BRIEF DESCRIPTION OF THE DRAWINGS [0031] To further a better understanding of the present invention, reference will now be made to the accompanying drawings, in which like elements are designated by like reference numerals. These drawings are not to be construed as limiting the present invention, but are presented by way of example only. FIG. 1 shows an exemplary block diagram illustrating a plurality of PCIe devices in communication with a host device, in accordance with an embodiment of the present invention. FIG. 2 illustrates a data structure representing uncloned condensed logic blocks, according to an embodiment of the present invention. [0034] Figure 3 illustrates tables showing master and cloned indirection data structure entries according to an embodiment of the present invention. FIG. 4 represents an exemplary module for improving the write-in-SSD functionality according to one embodiment of the present invention. Fig. 5 shows a flowchart illustrating an improved write copy functionality in an SSD, in accordance with an embodiment of the present invention. Fig. 6a shows a data structure input format structure of Master C Segments, in accordance with an embodiment of the present invention. Fig. 6B shows a data structure of C-segment Segment data structure input formats, in accordance with an embodiment of the present invention. Description [000] The present invention relates to an improved copy-to-write functionality. In some embodiments, this copy-to-write feature may include copies of the namespace. The PCIe Host Interface for SSD NVMe defines a concept of Namespaces, which are analogous to logical volumes supported by SAS RAID adapters (Redundant Array of Independent Disks). A namespace can be dedicated to a Virtual Machine (VM, Virtual Machine). In a SSD, the namespaces can be logically isolated from each other and can be securely deleted and reconverted without affecting other Namespaces. [0040] A namespace identifier may be included in a host access control issued by the host, in association with the LBA in that namespace. The SSD can use a data structure (for example, a look-up table, a tree, a hash table, a bitmap, etc.) to translate this combination of namespace and LBA 3033061 8 into an LBA global used internally to access the SSD. In some embodiments, references to an LBA may refer to this global LBA. Embodiments of the present invention describe a system and method for implementing an efficient function of 'Space Copy Names' which avoids duplicating the data on the SSD. This reduces the write amplification occurring in the SSD, thereby extending the SSD's lifetime while leading to better performance. Space copies of names are a form of "copy-to-write" functionality. On the copy function, a generated pointer points to the single copy on the media. A new copy on the media is generated and updated during a write. A copy function of the namespace requires efficient implementation of "write copy" on an SSD. Embodiments of the present invention may be applied to namespace copies. Embodiments of the present invention may also be applied to other embodiments of "write copy" for an SSD. By way of example, an "instant" copy may be used to create one-point images in time of a space of names, and embodiments of the present embodiment may be used to track copies. instant. Embodiments of the present invention provide an SSD indirection system (e.g., an absolute LBA table) or method for including multiple entries that point to the same physical location. Such an embodiment may allow efficient memory space recovery where multiple references exist. Tracking multiple references or manipulating multiple pointers (for example, on NAND and NAND flash data) can improve memory space recovery. Memory space recovery may be performed using metadata on the nonvolatile storage unit (e.g., NAND flash memory, NOR flash memory, etc.) which includes the host LBA. for the data. The memory space recovery algorithm can determine that sectors of the host are still valid by looking at these addresses in the indirection data structure (for example, a table, a tree, a hash, a topogram binary, etc.) to check if the data structure still points to the physical location. If this is not the case, the algorithm releases the block. One or more embodiments described herein provide an efficient representation of a duplicate indirection entry using a single flag and another indirection input format 3033061 9 which tracks one or more Duplicate host LBA addresses. One or more embodiments may use an absolute indirection lookup data structure for tracking multiple logical block addresses pointing to the same physical address. Other embodiments may be implemented using a hash table, a tree, or a composition based system for tracking duplicate LBAs. Techniques for improving the copy-to-write functionality in an SSD are discussed in more detail below. Referring now to the drawings, FIG. 1 is an exemplary functional diagram illustrating a PCIe device in communication with a host device, in accordance with an embodiment of the present invention. Improvements in copy-to-write functionality can be implemented in one or more computer technologies, for example as a host system 102, a host CPU 104, and a PCI root complex Express PCIe root complex 106. An express PCI switch 108 can communicately couple a plurality of targets (e.g., PCIe devices such as NVMe-based targets) such as Targets 110, 116 and 122 to host system 102 through express PCI root complex 106. Target 110 may contain an NVMe controller 112 and a nonvolatile storage unit 114. Target 116 may contain an NVMe controller 118 and a drive. The target 122 may include an NVMe controller 124 and a nonvolatile storage unit 126. The system memory 128 may contain memory-based resources accessible to the Host System 102 through the intermediary of the server. memory interface (for example, synchronous dynamic random access memory type three with double data rate (DDR3 SDRAM)). The system memory 128 may be in any suitable form, for example, without any limitation thereto, a semiconductor memory (e.g., a flash memory, or a semiconductor device (SSD )), an optical memory, and a magnetic memory. The system memory 128 may be volatile or non-volatile memory. The system memory 128 may contain one or more data structures. According to some embodiments, interface standards other than PCIe may be used for one or more portions, including, but not limited to, Advanced Serial Connection Technology (SATA, Serial). Advanced Technology Attachment), Advanced Technology Attachment (ATA), 5 Small Computer System Interface (SCSI), Extended PCI (PCI-X), Fiber Channel, SCSI Serial Attached SCSI (SAS), Secure Digital (SD), Embedded Multi-Media Card (EMMC), and Universal Flash Storage (UFS). The host system 102 may be in any suitable form, for example, without any limitation thereto, an enterprise server, a database host, a workstation, a computer personnel, a mobile phone, a gaming device, a personal digital assistant (PDA), an e-mail / text messaging device, a digital camera, a digital media player (eg MP3), GPS navigation, and a television system. The host system 102 and the target device may comprise additional components, which are not shown in Figure 1 to simplify the drawing. On the other hand, in some embodiments, not all the components shown are present. In addition, the various controllers, blocks, and interfaces can be implemented in any suitable manner. For example, a controller may be in the form of one or more of a microprocessor or processor and a computer readable medium that stores computer readable program code (eg, software or firmware) executable by the (micro) processor, for example, logic gates, switches, an Application Specific Integrated Circuit (ASIC), a programmable logic controller, and an integrated microcontroller. Referring to FIG. 2, a data structure representing uncloned condensed logic blocks is illustrated in accordance with an embodiment of the present invention. Eight condensed logic block inputs of 4 kilobytes are illustrated in this embodiment. These uncloned PLBs can map Logical Block Addresses (LBAs) to a physical address. As shown, LBAs 0-7 can be mapped to Physical Address Block 0, LBAs 7-15 can be mapped to Physical Address Block 1, LBAs 16-23 can be mapped to Block 3033061 11 of Physical Addresses 2, LBAs 24-31 can be mapped to Physical Address Block 3, LBAs 32-39 can be mapped to Physical Address Block 4, LBAs 40-47 can be mapped to Physical Address Block 5, LBAs 48-55 may be mapped to Physical Address Block 6, and LBAs 56-63 may be mapped to Physical Addresses Block 7. [0053] FIG. 3 illustrates tables representing master and cloned indirection data structure entries, in accordance with an embodiment of the present invention. As described with reference to FIG. 3, in some embodiments, write-copy enhancements may be implemented in an absolute indirection system. A PLB may be a "condensed logic block" in a lookup data structure (for example, an absolute indirection lookup table). A set of 8 consecutive PLBs aligned on 8 PLBs involved in a cloning operation may be referred to as "C-Chunk". A Segment C whose bearer data is marked by the PLBs suitable for that Segment C (i.e., the original copy) may be called "Master C Segment". Entries in the indirection data structure for all PLBs in a C-Segment can be grouped together to form a single "C-Entry". An entry C corresponding to a segment C whose data is on the support can be called entry C Mistress. Inputs C that describe LBA ranges that are copies of the master LBA range can be referred to as C Clone Inputs. One or more SSDs can define a PLB to track 4 KB of customer data plus metadata (for example 8x512 o sectors). In the embodiments presented below, a PLB may simply be an entry in a table. An indirection data structure entry may be extended (e.g., one bit) to facilitate write copying. An additional bit may be a "clone tracking" bit which may be set to 1 to indicate either that there are other PLBs for which this PLB is acting as the master copy, or that it is a clone that has some other PLB as its master copy. The remaining bits of the input of the indirection data structure whose clone tracking bit is set may or may not contain a NAND memory address (for example, as may be the case of an entry whose the bit is not set). The other possible data structure for clone tracking is followed with a coarser granularity than the typical PLB input, and includes fields for creating a linked list of cloned inputs and a pointer pointing to the master entrance. The space required for these additional fields can be obtained by using a single Input C to describe a larger 3033061 12 (eg 2x) LBA address segment than an uncloned indirection input. This compromise is reasonable because the cloned data tends to involve large partitions or file sets rather than individual host LBA addresses. The physical addresses of the individual host LBAs are distributed such that additional consultation is required for some LBAs. This frees up space to include master and clone pointers in each master and clone entry. However, the number of DRAM accesses to search for physical addresses is not significantly increased. As shown in Figure 3, the Master C-Input may contain the LBAs mapped to all the physical addresses 8-15, but only contains the actual mappings on the physical addresses 8-11, 14, and 15 (the mapping on physical addresses 12 and 13 can be obtained from the Clone Input C). As illustrated in the Clone Input C of Figure 3, mappings can be provided for the LBAs corresponding to the physical addresses 8-13. The two unmapped physical blocks in the M Master Input (Physical Addresses 12 and 13) provide the space needed for a Master Index 15 and a Next Index. The two unmapped physical blocks in Clone Input C (Physical Addresses 14 and 15) provide the space needed for a Master Index and a Next Index. A Master Index in a Mistress Entry C always points to itself. A Master Index in a Clone C Input always points to the M Master Input. A Next Index to the M Master Entry points to a first C Clone Entry in a string. A Next Clone Index 20 points to a next Clone C entry if there is more than one Clone C entry. If there is only one Clone Input C or if it is the last Clone Input C, the Next Index may point back to the C Master index (or may point to a special value indicating an end of the list such as a null pointer). This can be used to browse a Master Entry C and one or more C Clone entries. In embodiments using an absolute indirection data structure, a PLB (Physical Location Block) refers to an individual entry containing a physical NAND memory address in a single look-up table. A 4kbyte type PLB granularity (for example 8 * 512 o sectors) at a single input of the data structure. By way of example, a clone segment size of 8 PLB blocks will be considered - the average number of DRAM access required for purely random single sector accesses to a cloned range is 1.25. This number may be smaller with a larger clone size, the trade-off being between less granular clone boundaries and more NAND access required to 'unblock' a PLB block segment. If a read PLB read by a host points to a cloned input, the SSD must have 1) the physical address and 2) the LBA that was used when the data 5 was written. The physical address is split between the master and cloned inputs, optionally filling all available PLB entries with duplicate data to reduce the likelihood that the targeted LBA will require a second DRAM reading. For a number equal to 2, the master LBA can be computed based on the master pointer in each clone entry - this does not require additional DRAM access per design, and this master pointer (in combination with next clone pointer) can be cached from the original PLB lookup. In some embodiments, to hold additional information in an existing indirection data structure, cloning can only be continued with a granularity equal to any multiple of the PLB size. In some embodiments, the granularity may be selected as a multiple of a power of two of the size of the PLB to allow efficient calculation of the Segment C index corresponding to a given LBA. By way of example, the multiplier may be 8, but larger cloning granularities may be used. Cloning can involve cloning large LBA address ranges at one time (for example, all of a namespace), so that the penalty due to the use of one more large granularity is minimal. In some embodiments, the indirection data structure may comprise, integrated therewith, a circular linked list of one or more C segments that refer to the same data. In other embodiments, other forms of linked lists (e.g., a single-end linked list) may be used. The physical addresses describing the data of Segment C can be distributed among indirection entries for this list of Segments C. [0059] A Segment C whose data are physically on the support, marked by the PLBs that are suitable for this Segment. C (i.e., the original copy) may be referred to as "Master C Segment". Other C Segments that refer to the current time to the same data without storing a copy on the medium can be called "Clone C Segments". The entries of the indirection data structure for all PLBs in a C-Segment are grouped together to form a single "C-Input". For a Master C Segment, the C Input may have the format shown in Figure 6A. As illustrated, a master C-segment may contain physical addresses 0-3 (the first four physical addresses in a range), followed by physical addresses 6 and 7. The two missing physical addresses may be mapped into a Clone C-entry. and the two additional slots can be used to provide a Master Index and a Next Index. As illustrated, a "clone tracking" flag can be set to 1. This indicates to a memory space recovery process that the C entry should be ignored. For a Clone C Segment, the C Input may have the format shown in Figure 6B. As illustrated, the physical addresses 0-5 may be mapped and the physical addresses 6 and 7 may be missing. The two missing physical addresses can be mapped into the Master C Input and the two additional slots can be used to provide a Master Index and a Next Index. As illustrated, a 15 "indicator followed by a clone" can be set to 1. This indicates to a memory space recovery process that the C input should be ignored. In one or more embodiments, the NAND-Address may be the NAND address for an ith PLB of the Master C-Segment (where i = 0 represents the first PLB). A Master Index can be an indirection data structure index of the Master C Input 20 (divided by 8 since it occupies the space of 8 PLB entries). A Next Index can be an indirection data structure index for the next Clone C entry pointing to the same data (divided by 8 since it occupies the space of 8 PLB entries). If there are no more C Clone Inputs to represent, this Next Index may point back to the M Master Input. In some embodiments, this Next Index may point to a value indicating the end of the list (e.g., a null pointer). In some embodiments, one or more tests may be used to determine whether a C-Segment is a master entry. For example, a Segment C may be the master if and only if the Master Index of its C input points to the C Input itself. [0064] The relationship between a Master Entry C and a Clone Entry C through Master Indexes and Next Indexes enables the efficient execution of one or more of the following operations. To clone a set of 8 consecutive PLBs aligned on 8 PLBs, one or more methods may be used. For example, in one or more embodiments, the cloning of a set of PLB blocks may consist of: 1. Reading the 8 NAND addresses for the PLBs of the original copy to which it must be made reference when creating Master and Clone C-Inputs; 2. Create a Master C Input instead of the indirection inputs of the 8 original PLB blocks. The Next Index can point to the new Clone Input C; and 3. Create a Clone Input C instead of the indirection inputs of the 8 PLB blocks that will then act as a clone. The Next Index may point to the new Entrance C Mistress. To clone a Segment C into a new Segment C, one or more methods may be used. For example, in one or more embodiments, the cloning of a Segment C into a new Segment C may consist of: 1. If the source Segment C is a master, follow a Next Index of an Entry C 15 source to find a Clone Input C and copy it to the location of the new C Input. If the Source C Segment is not a master, copy the Source C Input to the location of the new C Input; 2. Update the Next Index of the new Entry C with Index Next current of the Entry C Mistress; 3. Update the Next Index of the Master Entry C so that it points to the new Entry C. [0067] To perform a read lookup on a PLB whose indirection entry includes a bit of positioned clone tracking, one or more methods may be used. For example, in one or more embodiments, performing a read lookup on a PLB having a positioned indirection bit may consist of: 1. Observing the entry C which contains the entry of indirection of this PLB. Determine whether or not this Entry C is a Master C Entry. On the basis of the determination, further determine whether the NAND address for the desired Master PLB is stored in this Input C. 2. If the NAND address is stored in the first C Input read, this NAND address and Master Index can be returned. The Master Index can be used to determine how many PLBs the data will be tagged without additional indirection requests. 3. If the NAND address is not stored in the first C Input read and if the first C Input read is a Master C Input, the Next Index can be tracked to find a Clone C Input that contains the NAND address required.
    [0005] This NAND address and the Master Index can be returned. 4. If the NAND address is not stored in the C Input read and if it is a Clone C Input, the Master Index can be tracked to find a Master C Entry that contains the necessary NAND address. This NAND address and the Master Index can be returned.
    [0006] 100681 To "unmount" a Clone C Segment, one or more techniques may be used. By way of example, in some embodiments, these techniques may include: 1. Determining if there is only one clone. For example, if the Next Index of the target Input C matches its Master Index and if the Next Index of the Input 20 C Master points to the target Input C, then there is only a single clone. Read C inputs for both the Master and Clone and overwrite the Master C Input with "normal" indirection entries for these PLBs. 2. If the Next Index of the Target C Entry does not match its Master Index or if the Next Index of the Master C Entry does not point to the Target Entry C, then 25 other clones are present . Eliminate this Input C from its circular list 3. In all cases, read the data for the Master C Segment and copy it to the Clone C Segment, overwriting the Clone C Inputs with normal indirection entries indicating the addresses. NAND of the new copy. For "unblocking" a C-master segment one or more techniques may be used. By way of example, in some embodiments these techniques may consist of: 1. Reading the Master Entry C and the first Clone Entry C; and 2. Read the data from a storage medium for the Master C-Segment and copy it to the first PLB Clone C-Segment by writing it to a new location in the storage medium and attaching the LBA metadata from the host to the host. Clone C segment corresponding; 3. If this first clone is the only clone (i.e., its Next Index is pointing back to the master), then overwrite the first Clone Input C with normal indirection entries pointing to the addresses. NAND for the copy that has just been created. Overwrite the Master C Entry with normal indirection entries pointing to PLBs of the original Master C Segment; 4. If "the first clone was not the only clone, remove the master from the circular linked list. Overwrite the first C Clone Entry with a new M Master Entry for the copy that has just been created. Overwrite other C Clone Entries with a new Clone C Entry for the newly created copy. This helps to favor the fact that the first Clone Input C of the old M Master Input becomes the new M Master Entry for itself and the remaining Clone C Entries. When an indirection update is required for a target PLB whose clone tracking bit is set, these techniques may consist, at an atomic level, in: 1. Declining the C segment of the PLB; and 2. Perform the indirection update normally. The memory space recovery can be implemented in such a way that the memory space recovery algorithm never rejects the data for any physical data whose PLB is marked by the clone tracking bit. in the indirection system. Specifically, the memory space recovery algorithm may consider all PLBs marked with a clone tracking bit to be "valid" data that requires movement rather than erasure. In one or more embodiments, a small counting Bloom filter could be stored in SRAM to track C segments present in the system.
    [0007] 5 When writing, if the Bloom filter can indicate that there is no risk that the PLB is part of a C Segment, then a direct update of the indirection system can be performed safely without first reading the current data structure entry. Since the clones tend to be large sequential ranges, the hash function used for a Bloom filter can be of the type: f (Index Input C) = Index Input C / Size of the Filter 10 rather than a random function. FIG. 4 illustrates an example of a module for improving the write copy functionality in an SSD, according to an embodiment of the present invention. As illustrated in FIG. 4, the write copy module 410 may contain an indirection creation module 412, an indirection management module 414, and an error handling module 416. [0074] The indirection creation module 412 can create one or more data structures for tracking copy-by-copy copies. A PLB can simply be an entry in a table. An indirection data structure entry may be extended (e.g., one bit) to facilitate write copying. An additional bit may be a "clone tracking" bit which may be set to 1 to indicate either that there are other PLBs for which this PLB is acting as the master copy, or that it is a clone that has some other PLB as its master copy. The remaining bits of the input of the indirection data structure whose clone tracking bit is set may or may not contain a NAND address (for example, as may be the case of an entry whose bit is not positioned).
    [0008] The alternative data structure for "clone tracking = 1" includes fields for creating a linked list of cloned entries and a pointer to the master entry. The space required for these additional fields is obtained by using a single entry to describe a larger (eg 2x) LBA address segment than an uncloned indirection entry. The indirection management module 414 may implement one or more operations using an indirection data structure. The indirection management module 3033061 19 414 can promote data cloning, cloned data reading, data decommissioning, and facilitate safe and efficient memory space recovery using one or more of the methods set forth above. with reference to FIG. 3. An error management module 416 may trap, log, report, and / or process one or more errors associated with the management of cloned data. Fig. 5 shows a flowchart illustrating an improved write copy functionality in an SSD, in accordance with an embodiment of the present invention. However, the process 500 is only presented as an example. The process 500 may be modified, for example, by having steps added, changed, eliminated, or rearranged. At step 502, the process can begin. At step 504, a Master Entry C can be created. A Segment C whose data is physically on the medium, marked by the appropriate PLBs for that Segment C (ie the original copy) can be called "Master C Segment". Other C-Segments that refer to the current time to the same data without storing a copy on the carrier may be referred to as "Clone C Segments". The entries of the indirection data structure for all PLBs in a C Segment are grouped together to form a single "C Input." For a C-master segment, the C-Input may have the format shown in Figure 6A. In step 506, a clone input C can be created. For Clone Segment C, Input C may have the format shown in Figure 6B. In one or more embodiments, the NAND address may be the NAND address for a PLB of the Master C-Segment (where i = 0 represents the first PLB). In step 508, a block may be assigned to indicate a Master Index. A Master Index can be an indirection data structure index of the M Mastered Input 25 (divided by 8 since it occupies the space of 8 PLB entries). The Master Index of both a Master C Entry and a Clone C Entry can point to a Master C Entry. In step 510, a block may be assigned to indicate a Next Index. A Next Index can be an indirection data structure index for the next Clone Entry 3033061 pointing to the same data (divided by 8 since it occupies the space of 8 PLB entries). If there are no more C Clone Inputs to represent, this Next Index may point back to the M Master Input. In some embodiments, one or more tests may be used to determine whether a Segment C is a master entry. For example, a Segment C may be the master if and only if the Master Index of its C input points to the C Input itself. In step 512, the method 500 may be terminated. Other embodiments fall within the scope and spirit of the invention. By way of example, the functionality described above may be implemented by means of software, hardware, firmware, fixed wiring, or combinations of any of these forms. One or more computer processors operating in accordance with instructions may implement the functions associated with the enhanced write-to-write functionality in an SSD in accordance with the present invention as described above. If so, it is within the scope of the present invention that such instructions are stored on one or more processor-readable non-transitory storage media (e.g., a magnetic disk or other storage medium). In addition, function implementing modules may also be physically located at various positions, including the fact that they are distributed in such a way that parts of the functions are implemented at different physical locations. The scope of the present invention should not be construed as being limited to the particular embodiments described herein. Indeed, various other embodiments and various other variations of the present invention, in addition to those described herein, will be apparent to those of ordinary skill in the art from the foregoing description and the accompanying drawings. Consequently, these other embodiments and variants will have to be considered as falling within the scope of the present invention. In addition, although the present invention has been described herein in the context of a particular embodiment in a particular environment for a particular application, one of ordinary skill in the art will appreciate that its utility is not limited to those skilled in the art. and that the present invention may be advantageously implemented in any number of environments for any number of applications. Accordingly, the claims set forth below will have to be appreciated in their broadest sense and in accordance with the spirit of the present invention as described herein.
    权利要求:
    Claims (25)
    [0001]
    REVENDICATIONS1. A method for providing enhanced write copy functionality in an SSD comprising: providing, in the memory of a device, an indirection data structure comprising: a master input for cloned data, the input master having a reference to one or more indexes; a clone entry for the cloned data, the cloned entry including at least one of: a reference to a master index, a reference to a next index, and a value indicating an end of a data structure ; and browse, using a computer processor, one or more copies of the cloned data using one or more of the references.
    [0002]
    The method of claim 1, wherein the indirection data structure comprises a plurality of physical addresses.
    [0003]
    The method of claim 1, wherein the indirection data structure is part of a circular linked list, the master entry for cloned data including a reference to a master index and a reference to a next index. 20
    [0004]
    The method of claim 1, wherein the indirection data structure is part of a circular linked list, the clone entry for the cloned data including a reference to the master index and a reference to a next index. . 25
    [0005]
    The method of claim 1, wherein the indirection data structure is part of a single-end linked list, an entry contained in an index providing an indication that the index is a master index.
    [0006]
    The method of claim 1, wherein the references include inputs in an absolute indirection table for logical block addressing.
    [0007]
    The method of claim 1, wherein the references include entries in a tree data structure for logical block addressing. 3033061 23
    [0008]
    The method of claim 1, wherein the enhanced copy-to-write functionality includes enhanced namespace copy functionality.
    [0009]
    The method of claim 1, further comprising positioning an indicator for one or more condensed logic blocks to indicate that said one or more condensed logic blocks are cloned.
    [0010]
    The method of claim 1, wherein a master index of the master entry points to the master entry.
    [0011]
    The method of claim 3, wherein the master index of the cloned input points to the master input.
    [0012]
    The method of claim 4, wherein the next index of a last cloned entry in a data structure points to the master entry.
    [0013]
    The method of claim 4, further comprising: determining that the clone input for the cloned data is a single clone input, the determination of: determining that the next index of the cloned input matches the clone input; master index of the cloned entry; determine that the next index of the master entry points to the clone entry; disabling the clone input of the cloned data by setting the next index of the clone input to an indirection input indicating a condensed logic block and setting the master index entry to an indirection input indicating a block condensed logic; and disabling the master entry of the cloned data by setting the next index of the master entry to a first indirection entry indicating a first condensed logical block of an original master entry and setting the master index of the master entry a second indirection input indicating a second condensed logic block of the original master input.
    [0014]
    The method of claim 4, further comprising: determining that the clone input for the cloned data is one of a plurality of clone inputs, the determination of determining at least one the following: that the next index of the cloned entry does not match the master index of the cloned entry; and that the next index of the master entry does not point to the clone entry; and disabling the clone input of the cloned data by setting the next index of a previous entry to point to an entry indicated by the next index of the clone entry.
    [0015]
    The method of claim 1, further comprising: examining an input during a memory space recovery process; Determining that the entry contains a cloned flag; and determining that the input involved in the memory space recovery process is a valid input not to be deleted based on the determination that the entry contains the cloned flag. 15
    [0016]
    A computer program product consisting of a series of executable instructions on a computer, wherein the computer program product executes a process for providing enhanced copy-to-write functionality in an SSD; the computer program implementing the steps of: providing, in the memory of a device, an indirection data structure comprising: a master entry for cloned data, the master entry including a reference to one or more index; a clone entry for the cloned data, the cloned entry including at least one of: a reference to a master index, a reference to a next index, and a value indicating an end of a data structure ; and browse, using a computer processor, one or more copies of the cloned data using one or more of the references.
    [0017]
    A system for providing enhanced copy-to-write functionality in an SSD, the system comprising: a first device; the first device comprising stored instructions, which are stored in memory, the instructions comprising: an instruction for providing, in the memory of the first device, an indirection data structure comprising: a master entry for cloned data, the master entry having a reference to one or more indexes; A clone entry for the cloned data, the cloned entry including at least one of: a reference to a master index, a reference to a next index, and a value indicating an end of a data structure ; and browse, using a computer processor, one or more copies of the cloned data using one or more of the references. 10
    [0018]
    The system of claim 17, wherein the indirection data structure comprises a plurality of physical addresses.
    [0019]
    The system of claim 17, wherein the indirection data structure is part of a circular linked list, the master entry for cloned data including a reference to a master index and a reference to a next index. 15
    [0020]
    The system of claim 17, wherein the indirection data structure is part of a circular linked list, the clone input for the cloned data including a reference to the master index and a reference to a next index. . 20
    [0021]
    The system of claim 17, wherein the indirection data structure is part of a single-end linked list, an entry contained in an index providing an indication that the index is a master index.
    [0022]
    The system of claim 17, wherein the references include inputs in an absolute indirection table for logical block addressing.
    [0023]
    The system of claim 17, wherein the first device comprises an Express Peripheral Component Interconnection (PCIe) device. 30
    [0024]
    The system of claim 17, further comprising an instruction for positioning an indicator for one or more condensed logic blocks to indicate that said one or more condensed logic blocks are cloned. 3033061 26
    [0025]
    The system of claim 20, wherein the master index of the master input and the master index of the cloned input point to the master input and the next index of a last cloned input in a master structure. data points to the master entry.
    类似技术:
    公开号 | 公开日 | 专利标题
    FR3033061A1|2016-08-26|
    US10089191B2|2018-10-02|Selectively persisting application program data from system memory tonon-volatile data storage
    US11249951B2|2022-02-15|Heuristic interface for enabling a computer device to utilize data property-based data placement inside a nonvolatile memory device
    KR101480659B1|2015-01-09|Two-level system main memory
    JP5592942B2|2014-09-17|Shortcut I / O in virtual machine system
    US8103847B2|2012-01-24|Storage virtual containers
    US10261703B2|2019-04-16|Sharing read-only data among virtual machines using coherent accelerator processor interface | enabled flash
    US11169968B2|2021-11-09|Region-integrated data deduplication implementing a multi-lifetime duplicate finder
    US7945724B1|2011-05-17|Non-volatile solid-state memory based adaptive playlist for storage system initialization operations
    US20170199674A1|2017-07-13|Data Deduplication With Support for Both Thick and Thin Provisioning of Storage Objects
    US10055304B2|2018-08-21|In-memory continuous data protection
    US8825970B1|2014-09-02|System and method for mounting a storage volume utilizing a block reference list
    US10817624B2|2020-10-27|Memory system and storage device capable of permanently deleting data stored in a non-volatile memory
    US11263090B2|2022-03-01|System and method for data packing into blobs for efficient storage
    US11016684B1|2021-05-25|System and method for managing data and metadata where respective backing block devices are accessed based on whether request indicator indicates the data or the metadata and accessing the backing block devices without file system when the request indicator is not included in request
    CN111339046A|2020-06-26|Data writing, reading and deleting method and device for file
    US20170052705A1|2017-02-23|Listing storage media
    同族专利:
    公开号 | 公开日
    GB2537012A|2016-10-05|
    US11226747B2|2022-01-18|
    US20200150883A1|2020-05-14|
    CN105912475A|2016-08-31|
    US9880755B2|2018-01-30|
    GB2537012B|2019-07-03|
    JP2016157441A|2016-09-01|
    GB201601965D0|2016-03-16|
    KR20160103945A|2016-09-02|
    US10540106B2|2020-01-21|
    FR3033061B1|2021-03-05|
    DE102016001591A1|2016-08-25|
    KR101813786B1|2018-01-02|
    US20160246521A1|2016-08-25|
    US20180150249A1|2018-05-31|
    JP6218869B2|2017-10-25|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US4742450A|1986-01-16|1988-05-03|International Business Machines Corporation|Method to share copy on write segment for mapped files|
    US5481694A|1991-09-26|1996-01-02|Hewlett-Packard Company|High performance multiple-unit electronic data storage system with checkpoint logs for rapid failure recovery|
    US5574905A|1994-05-26|1996-11-12|International Business Machines Corporation|Method and apparatus for multimedia editing and data recovery|
    US5815649A|1995-10-20|1998-09-29|Stratus Computer, Inc.|Distributed fault tolerant digital data storage subsystem for fault tolerant computer system|
    US6219770B1|1998-03-23|2001-04-17|Compaq Computer Corporation|Method and apparatus for managing copy on write operations in a virtual memory|
    FI991336A|1999-06-10|2000-12-11|Nokia Networks Oy|Procedure for reviving a disk-protected database|
    US6751583B1|1999-10-29|2004-06-15|Vast Systems Technology Corporation|Hardware and software co-simulation including simulating a target processor using binary translation|
    US6779095B2|2000-06-19|2004-08-17|Storage Technology Corporation|Apparatus and method for instant copy of data using pointers to new and original data in a data location|
    US6976021B2|2001-07-19|2005-12-13|Riverstone Networks, Inc.|Method, system, and computer program product for managing a re-usable resource with linked list groups|
    US6748504B2|2002-02-15|2004-06-08|International Business Machines Corporation|Deferred copy-on-write of a snapshot|
    US7249352B2|2002-08-22|2007-07-24|International Business Machines Corporation|Apparatus and method for removing elements from a linked list|
    US7529897B1|2003-12-31|2009-05-05|Vmware, Inc.|Generating and using checkpoints in a virtual computer system|
    US20070093124A1|2005-10-20|2007-04-26|Lsi Logic Corporation|Methods and structure for SAS expander optimization of SAS wide ports|
    US7774316B2|2005-11-30|2010-08-10|Oracle International Corp.|Filesystem snapshot enhancement to improve system performance|
    US7499961B2|2006-01-12|2009-03-03|Sun Microsystems, Inc.|Method and apparatus for limiting the size and facilitating maintenance of remembered sets in a space incremental garbage collector|
    US7673185B2|2006-06-08|2010-03-02|Dot Hill Systems Corporation|Adaptive SAS PHY configuration|
    US8195912B2|2007-12-06|2012-06-05|Fusion-io, Inc|Apparatus, system, and method for efficient mapping of virtual and physical addresses|
    US7941470B2|2007-03-29|2011-05-10|Vmware, Inc.|Synchronization and customization of a clone computer|
    US8706976B2|2007-08-30|2014-04-22|Commvault Systems, Inc.|Parallel access virtual tape library and drives|
    US7912995B1|2007-12-20|2011-03-22|Emc Corporation|Managing SAS topology|
    US7941692B2|2007-12-31|2011-05-10|Intel Corporation|NAND power fail recovery|
    US8190835B1|2007-12-31|2012-05-29|Emc Corporation|Global de-duplication in shared architectures|
    US7953778B2|2008-05-20|2011-05-31|International Business Machines Corporation|Efficient support of consistent cyclic search with read-copy update and parallel updates|
    US20120311243A1|2008-05-30|2012-12-06|Ite Tech. Inc.|Method for increasing reliability of data accessing for a multi-level cell type non-volatile memory|
    JP5156518B2|2008-07-23|2013-03-06|株式会社日立製作所|Storage control apparatus and method|
    JP5108667B2|2008-07-23|2012-12-26|株式会社日立製作所|Remote copy system and remote site power saving method|
    US8200922B2|2008-12-17|2012-06-12|Netapp, Inc.|Storage system snapshot assisted by SSD technology|
    EP2433226B1|2009-06-26|2015-08-12|Simplivity Corporation|File system|
    US20110161298A1|2009-12-29|2011-06-30|Grobman Steven L|System and method for opportunistic re-imaging using cannibalistic storage techniques on sparse storage devices|
    US8447943B2|2010-02-24|2013-05-21|Hitachi, Ltd.|Reduction of I/O latency for writable copy-on-write snapshot function|
    US9104546B2|2010-05-24|2015-08-11|Silicon Motion Inc.|Method for performing block management using dynamic threshold, and associated memory device and controller thereof|
    US8621143B2|2011-04-15|2013-12-31|Oracle International Corporation|Elastic data techniques for managing cache storage using RAM and flash-based memory|
    US8868869B2|2011-08-08|2014-10-21|International Business Machines Corporation|Enhanced copy-on-write operation for solid state drives|
    US8527544B1|2011-08-11|2013-09-03|Pure Storage Inc.|Garbage collection in a storage system|
    JP5816303B2|2011-09-13|2015-11-18|株式会社日立製作所|Storage system including flash memory and storage control method|
    JP5776474B2|2011-09-29|2015-09-09|富士通株式会社|Storage device, storage control device, and copy destination data access method|
    US8930307B2|2011-09-30|2015-01-06|Pure Storage, Inc.|Method for removing duplicate data from a storage array|
    US8935499B2|2011-10-17|2015-01-13|International Business Machines Corporation|Interface for management of data movement in a thin provisioned storage system|
    US8566543B2|2011-12-19|2013-10-22|Hitachi, Ltd.|Computer system and reclamation control method|
    US9229853B2|2011-12-20|2016-01-05|Intel Corporation|Method and system for data de-duplication|
    US9152570B2|2012-02-27|2015-10-06|Vmware, Inc.|System and method for supporting finer-grained copy-on-write page sizes|
    US8843666B2|2012-03-02|2014-09-23|Lsi Corporation|Method for optimizing wide port power management in a SAS topology|
    US8850145B1|2012-03-30|2014-09-30|Emc Corporation|Managing consistency groups in storage systems|
    CN103544077B|2012-07-17|2016-12-07|华为技术有限公司|Data processing method and device, shared storage device|
    US8924751B2|2012-07-31|2014-12-30|Hewlett-Packard Development Company, L.P.|SAS power management|
    US8959374B2|2012-07-31|2015-02-17|Hewlett-Packard Development Company, L.P.|Power management for devices in a data storage fabric|
    US8862810B2|2012-09-27|2014-10-14|Arkologic Limited|Solid state device write operation management system|
    US9436720B2|2013-01-10|2016-09-06|Pure Storage, Inc.|Safety for volume operations|
    JP6109967B2|2013-02-21|2017-04-05|ヒタチ データ システムズ エンジニアリング ユーケー リミテッドＨｉｔａｃｈｉ Ｄａｔａ Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｋ Ｌｉｍｉｔｅｄ|Replicating cloned objects at the object level in a data storage system|
    US20150006814A1|2013-06-28|2015-01-01|Western Digital Technologies, Inc.|Dynamic raid controller power management|
    US9588882B2|2013-12-02|2017-03-07|Intel Corporation|Non-volatile memory sector rotation|
    US9170746B2|2014-01-07|2015-10-27|Netapp, Inc.|Clustered raid assimilation management|
    US9880755B2|2015-02-25|2018-01-30|Western Digital Technologies, Inc.|System and method for copy on write on an SSD|DE19720505A1|1997-05-15|1998-11-19|Hoechst Diafoil Gmbh|Biaxially oriented polyester film with high oxygen barrier, process for its production and use|
    US9880755B2|2015-02-25|2018-01-30|Western Digital Technologies, Inc.|System and method for copy on write on an SSD|
    US10719479B2|2016-06-28|2020-07-21|Netapp, Inc.|Data unit cloning in memory-based file systems|
    US10031689B2|2016-09-15|2018-07-24|Western Digital Technologies, Inc.|Stream management for storage devices|
    KR20180038813A|2016-10-07|2018-04-17|삼성전자주식회사|Storage device capable of performing peer-to-peer communication and data storage system including the same|
    JP6783645B2|2016-12-21|2020-11-11|キオクシア株式会社|Memory system and control method|
    US10268620B2|2016-12-23|2019-04-23|Ati Technologies Ulc|Apparatus for connecting non-volatile memory locally to a GPU through a local switch|
    US11061585B1|2017-10-19|2021-07-13|EMC IP Holding Company, LLC|Integration of NVMe device with DRAM cache system and method|
    US10521137B1|2017-10-31|2019-12-31|EMC IP Holding Company LLC|Storage device array integration of dual-port NVMe device with DRAM cache and hostside portion of software stack system and method|
    法律状态:
    2017-02-27| PLFP| Fee payment|Year of fee payment: 2 |
    2018-01-11| PLFP| Fee payment|Year of fee payment: 3 |
    2020-01-13| PLFP| Fee payment|Year of fee payment: 5 |
    2020-04-24| TP| Transmission of property|Owner name: WESTERN DIGITAL TECHNOLOGIES, INC., US Effective date: 20200319 |
    2020-06-19| PLSC| Publication of the preliminary search report|Effective date: 20200619 |
    2021-01-13| PLFP| Fee payment|Year of fee payment: 6 |
    2021-12-17| PLFP| Fee payment|Year of fee payment: 7 |
    优先权:
    申请号 | 申请日 | 专利标题
    US14/630,863|US9880755B2|2015-02-25|2015-02-25|System and method for copy on write on an SSD|
    [返回顶部]